﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading;

namespace TribesPSO
{
    /// <summary>
    /// A multi threaded (partial) implementation of SearchSpace
    /// </summary>
    /// <remarks>
    /// The performance of the multithreaded search space is actually worse than the default search space with regards to
    /// the number of evaluations that it takes to optimize a problem.  For the Rosenbrock problem, the difference is
    /// about 10%.  On the upside, the execution time is roughly the same on a quad core system running 4 threads.
    /// 
    /// Where the multithreaded search space IS useful is for optimizations of objective functions that are computationally
    /// intensive.  For example, a least squares fit of discrete data points.  In the case where the objective function is in
    /// the slow path of execution, I've seen a factor 2 or 3 speed-up on a quad core system running 4 threads.  Again, the
    /// number of evaluations will be higher, but the execution time will be lower
    /// 
    /// Note to inheritors.  When implementing the GenerateParticleAtPosition method, make sure each created particle gets
    /// its own random number generator.  Also if you're not using one of the default library particle implementations, make sure
    /// the implementation  you're using can have multiple particles in a neighborhood moving at the same time.
    /// </remarks>
    public abstract class MultithreadedSearchSpace<TParticle> : SearchSpace<TParticle> where TParticle : Particle
    {
        private readonly int threadCount;

        /// <summary>
        /// Gets the number of threads that were specified in the MultithreadedSearchSpace constructor
        /// </summary>
        protected int ThreadCount { get { return threadCount; } }

        /// <summary>
        /// Constructs a new multi threaded search space that will use the same number of threads as there are logical processors in the
        /// host environment.
        /// </summary>
        /// <param name="objectiveFunction"></param>
        protected MultithreadedSearchSpace(IObjectiveFunction objectiveFunction)
            : this(objectiveFunction, Environment.ProcessorCount) { }

        /// <summary>
        /// Constructs a new multi threaded search space
        /// </summary>
        /// <param name="objectiveFunction"></param>
        /// <param name="threadCount">
        /// The number of threads to use to move particles.  This value must be greater than
        /// or equal to 1 and less than or equal to 64
        /// </param>
        /// <exception cref="ArgumentOutOfRangeException">Thrown if threadCount is less than 1 or greater than 64</exception>
        protected MultithreadedSearchSpace(IObjectiveFunction objectiveFunction, int threadCount)
            : base(objectiveFunction)
        {
            if (threadCount < 1 || threadCount > 64)
                throw new ArgumentOutOfRangeException(
                    "threadCount",
                    threadCount,
                    "Thread count must be greater than or equal to 1 and less than or equal to 64");
            this.threadCount = threadCount;
        }

        /// <summary>
        /// Moves all of the particles in the search space, but uses multiple threads to take advantage of systems with
        /// multiple processors.  The particles are split up into N groups where N is the number of threads 
        /// we'll be spooling up.  The particles will run serially within their groups, but the groups will be processed
        /// in parallel.
        /// </summary>
        /// <remarks>
        /// Race conditions will make this a bit non deterministic, but since each particle has its own RNG
        /// in a multi threaded search space, we already lost the ability to run the optimization deterministically
        /// by specifying the RNG seed to the particles.  The base particle's move implementation will work fine
        /// if particles are moved in parallel.  It's not ok to have two threads call move on the same particle at the same
        /// time.
        /// </remarks>
        protected override void Move()
        {
            List<WaitHandle> WaitHandles = new List<WaitHandle>();
            int particlesPerThread = (int)Math.Ceiling((double)this.SwarmSize / (double)threadCount);

            var ToBeMoved = this.Tribes.InRandomOrder(this.RandomNumberGenerator).SelectMany(o => o.TribeMembers);

            foreach (var group in ToBeMoved.Split(particlesPerThread))
            {
                WaitHandle signal = MoveParticlesOnWorkerThread(group);
                WaitHandles.Add(signal);
            }
            WaitHandle.WaitAll(WaitHandles.ToArray());
        }

        /// <summary>
        /// Moves all of the particles in ToMove on serially on a worker thread and signals
        /// the when they've all been moved.  The particle list is captured by the worker thread
        /// so it shouldn't change once it's been passed to this method
        /// </summary>
        /// <param name="ToMove">A list of particles to move on a worker thread</param>
        /// <returns>A wait handle that will signal once all of the particles have been moved</returns>
        private static WaitHandle MoveParticlesOnWorkerThread(IEnumerable<Particle> ToMove)
        {
            ManualResetEvent resetEvent = new ManualResetEvent(false);
            Action<object> del = delegate(object unused)
            {
                foreach (Particle p in ToMove)
                {
                    p.Move();
                }
                resetEvent.Set();
            };
            ThreadPool.QueueUserWorkItem(new WaitCallback(del));
            return resetEvent;
        }
    }
}
